<!DOCTYPE html>



  


<html class="theme-next muse use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="Map,HashMap,">










<meta name="description" content="HashMap 一个基于哈希表的 Map 接口实现，提供能够存储键值对的类。">
<meta name="keywords" content="Map,HashMap">
<meta property="og:type" content="article">
<meta property="og:title" content="HashMap">
<meta property="og:url" content="http://sangaizhi.gitee.io/2018/11/16/2018-11-16-hashmap/index.html">
<meta property="og:site_name" content="sangaizhi-blog">
<meta property="og:description" content="HashMap 一个基于哈希表的 Map 接口实现，提供能够存储键值对的类。">
<meta property="og:locale" content="zh-Hans">
<meta property="og:image" content="http://tech.meituan.com/img/java-hashmap/hashMap%E5%86%85%E5%AD%98%E7%BB%93%E6%9E%84%E5%9B%BE.png">
<meta property="og:image" content="http://tech.meituan.com/img/java-hashmap/hashMap%20put%E6%96%B9%E6%B3%95%E6%89%A7%E8%A1%8C%E6%B5%81%E7%A8%8B%E5%9B%BE.png">
<meta property="og:image" content="http://tech.meituan.com/img/java-hashmap/hashMap%201.8%20%E5%93%88%E5%B8%8C%E7%AE%97%E6%B3%95%E4%BE%8B%E5%9B%BE1.png">
<meta property="og:image" content="http://tech.meituan.com/img/java-hashmap/hashMap%201.8%20%E5%93%88%E5%B8%8C%E7%AE%97%E6%B3%95%E4%BE%8B%E5%9B%BE2.png">
<meta property="og:image" content="http://tech.meituan.com/img/java-hashmap/jdk1.8%20hashMap%E6%89%A9%E5%AE%B9%E4%BE%8B%E5%9B%BE.png">
<meta property="og:updated_time" content="2018-12-11T13:18:36.011Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="HashMap">
<meta name="twitter:description" content="HashMap 一个基于哈希表的 Map 接口实现，提供能够存储键值对的类。">
<meta name="twitter:image" content="http://tech.meituan.com/img/java-hashmap/hashMap%E5%86%85%E5%AD%98%E7%BB%93%E6%9E%84%E5%9B%BE.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Muse',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://sangaizhi.gitee.io/2018/11/16/2018-11-16-hashmap/">





  <title>HashMap | sangaizhi-blog</title>
  








</head>

<body itemscope="" itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope="" itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">sangaizhi-blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle"></p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            关于
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope="" itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://sangaizhi.gitee.io/2018/11/16/2018-11-16-hashmap/">

    <span hidden itemprop="author" itemscope="" itemtype="http://schema.org/Person">
      <meta itemprop="name" content="sangaizhi">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope="" itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="sangaizhi-blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">HashMap</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2018-11-16T17:28:49+08:00">
                2018-11-16
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope="" itemtype="http://schema.org/Thing">
                  <a href="/categories/Collection/" itemprop="url" rel="index">
                    <span itemprop="name">Collection</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>HashMap 一个基于哈希表的 Map 接口实现，提供能够存储键值对的类。<br><a id="more"></a></p>
<h4 id="一、HashMap-的存储结构"><a href="#一、HashMap-的存储结构" class="headerlink" title="一、HashMap 的存储结构"></a>一、HashMap 的存储结构</h4><pre><code>HashMap 的存储结构是使用 **数组+链表+红黑树** 实现的。
</code></pre><p>   <img src="http://tech.meituan.com/img/java-hashmap/hashMap%E5%86%85%E5%AD%98%E7%BB%93%E6%9E%84%E5%9B%BE.png" alt="image"><br>   1、HashMap 中有一个 <strong>Node[] table</strong> 字段，就是 哈希桶数组，<strong>Node</strong> 内部类实现了 Map.Entry 接口，<br>   本质是一个键值对的映射。上图中的每一个小黑点就是一个 Node 对象。</p>
<p>   2、HashMap 就是使用哈希表来存储数据的。HashMap 为了解决元素冲突，采用数组+链表相结合的方式存储元素。<br>   即在每一个数组元素上都挂一个链表。当数据被 Hash 后，可以根据 key 经过 hash 算法（把key 的 hash 值<br>   经过高位运算）计算后的结果来得到数据应该存放在数组的哪个位置，然后把数据存放在下标元素对应的链表上。<br>   具体过程如下：<br>   <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">// hash 算法，取 key 的 hash 值</span><br><span class="line">static final int hash(Object key) &#123;</span><br><span class="line">    int h;</span><br><span class="line">    return (key == null) ? 0 : (h = key.hashCode()) ^ (h &gt;&gt;&gt; 16);</span><br><span class="line">&#125;</span><br><span class="line"> (table.length - 1) &amp; hash]   // 确定数组的下标</span><br></pre></td></tr></table></figure></p>
<p>   在定位元素的存储位置时，可能会发生 Hash碰撞（两个 key 定位到相同的位置）。当然，hash 算法结算结果越分散，<br>   Hash 碰撞的概率就会越小，map 的存储效率就会越高。另外，如果哈希桶数组越大，碰撞的概率也会相应减少。<br>   所以，需要在空间和时间上做平衡，根据实际情况确定哈希桶数组的大小，并在此基础上设计 hash 算法来减少碰撞。<br>   HashMap 通过扩容机制来减少碰撞。</p>
<h4 id="二、HashMap-中-put-方法的介绍"><a href="#二、HashMap-中-put-方法的介绍" class="headerlink" title="二、HashMap 中 put() 方法的介绍"></a>二、HashMap 中 put() 方法的介绍</h4><p>   总体过程如下图：<img src="http://tech.meituan.com/img/java-hashmap/hashMap%20put%E6%96%B9%E6%B3%95%E6%89%A7%E8%A1%8C%E6%B5%81%E7%A8%8B%E5%9B%BE.png" alt="image"><br>   1、判断键值对数组是否为空或者长度为0，否则执行 resize() 方法进行扩容，并返回扩容后的大小。<br>   2、根据 key 计算 hash值得到带插入的数组索引 i,<br>   如果键值对数组对应索引位置为空，则直接新建一个键值对节点，放在该位置。<br>   3、判断 table[i] 的链表中的第一个元素的 key 和 hash 值是否与 新加的元素一样（通过 hashCode()<br>   和 equals() 方法），如果一样，直接覆盖原值。<br>   4、判断 table[i] 是否为 treeNode, 即 table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对。<br>   5、遍历 table[i] 的链表，判断链表的长度是否大于 TREEIFY_THRESHOLD(8)，是的话就把链表转成红黑树，<br>   在红黑树中执行插入操作，否则进行链表的插入操作，在遍历的过程中如果发现 key 已经存在，则直接覆盖value。<br>   6、插入成功后，判断实际存在的键值对数量 size 是否超过了最大容量 threshold，如果超过则进行扩容。<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br></pre></td><td class="code"><pre><span class="line"> <span class="comment">// onlyIfAbsent 重写旧值得条件，当对应key已经存在，并且值不为null的情况是否可以覆盖重写，</span></span><br><span class="line"> <span class="comment">// true 表示不重写，false 表示重写</span></span><br><span class="line"> <span class="function"><span class="keyword">final</span> V <span class="title">putVal</span><span class="params">(<span class="keyword">int</span> hash, K key, V value, <span class="keyword">boolean</span> onlyIfAbsent,</span></span></span><br><span class="line"><span class="function"><span class="params">               <span class="keyword">boolean</span> evict)</span> </span>&#123;</span><br><span class="line">    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; <span class="keyword">int</span> n, i;</span><br><span class="line">    <span class="keyword">if</span> ((tab = table) == <span class="keyword">null</span> || (n = tab.length) == <span class="number">0</span>)</span><br><span class="line">        n = (tab = resize()).length; <span class="comment">// 1</span></span><br><span class="line">    <span class="keyword">if</span> ((p = tab[i = (n - <span class="number">1</span>) &amp; hash]) == <span class="keyword">null</span>) <span class="comment">// 2</span></span><br><span class="line">        tab[i] = newNode(hash, key, value, <span class="keyword">null</span>);</span><br><span class="line">    <span class="keyword">else</span> &#123;  <span class="comment">// 存在</span></span><br><span class="line">        Node&lt;K,V&gt; e; K k;</span><br><span class="line">        <span class="keyword">if</span> (p.hash == hash &amp;&amp;  ((k = p.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))  <span class="comment">// 3</span></span><br><span class="line">            e = p;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (p <span class="keyword">instanceof</span> TreeNode)  <span class="comment">// 4</span></span><br><span class="line">            e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(<span class="keyword">this</span>, tab, hash, key, value);</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> binCount = <span class="number">0</span>; ; ++binCount) &#123;</span><br><span class="line">                <span class="keyword">if</span> ((e = p.next) == <span class="keyword">null</span>) &#123;</span><br><span class="line">                    p.next = newNode(hash, key, value, <span class="keyword">null</span>);</span><br><span class="line">                    <span class="keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD - <span class="number">1</span>) <span class="comment">// -1 for 1st</span></span><br><span class="line">                        treeifyBin(tab, hash);</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">                    ((k = e.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                p = e;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 覆盖 value</span></span><br><span class="line">        <span class="keyword">if</span> (e != <span class="keyword">null</span>) &#123; <span class="comment">// existing mapping for key</span></span><br><span class="line">            V oldValue = e.value;</span><br><span class="line">            <span class="keyword">if</span> (!onlyIfAbsent || oldValue == <span class="keyword">null</span>)</span><br><span class="line">                e.value = value;  </span><br><span class="line">            afterNodeAccess(e);</span><br><span class="line">            <span class="keyword">return</span> oldValue;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    ++modCount;</span><br><span class="line">    <span class="keyword">if</span> (++size &gt; threshold) <span class="comment">// 6</span></span><br><span class="line">        resize();</span><br><span class="line">    afterNodeInsertion(evict);</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h4 id="三、HashMap-的-扩容机制（resize）"><a href="#三、HashMap-的-扩容机制（resize）" class="headerlink" title="三、HashMap 的 扩容机制（resize）"></a>三、HashMap 的 扩容机制（resize）</h4><pre><code>HashMap 在键值对超出最大容量阈值限制（size * loadFactor），会自动重新计算容量。哈希桶数组扩容方法
就是使用一个新的大数组代替已有的小数组。
1、复制旧的哈希桶数组
2、修改 HashMap 的容量及阈，有以下几种情况
  2.1、如果 HashMap 已经初始化（旧的容量大于0），就判断以下条件：
    2.1.1、如果旧的哈希桶数据大小已经超过 1 &lt;&lt; 30 (2^30),则把新的容量阈值(threshold)修改为
    Integer的最大值，这样的话，下次就不会扩容了。
    2.1.2、把新的容量设置为旧容量的两倍，如果旧的容量要大于初始容量并且新的容量小于 2^30 ，
    则会更新新的阈值为就阈值的两倍。（如果执行了该判断（不论结果如何），HaspMap 的容量就会扩大两倍，
    如果判断结果为true,那么阈值也会翻倍）。
  2.2、在旧容量小于等于0并且旧阈值大于0的情况下(旧容量被旧的阈值重置过)，就把旧的阈值设置为新的容量。
  2.3、在其他情况下，就把容量和阈值设置为默认值；
4、如果旧的阈值大于0（初始容量被阈值重置过），就把旧的阈值大小设置新的容量大小.
5、复制移动 HashMap 中的元素，把每个bucket都移动到新的buckets中。
  5.1、把 HashMap 中的哈希桶数组设置为一个空的新的数组，后续会把 HashMap 中的元素放到这个新数组中。
  5.2、遍历之前的哈希桶数组，如果遍历的当前位置有数据，才会执行数据移动操作。
    5.2.1、第一种情况，如果当前位置 bucket 中只有一个数据，则直接把这个元素移动新的哈希桶数组对应的位置。
    5.2.2、第二种情况，如果当前位置的 bucket 是一个红黑树。就把这个红黑树进行拆分成两个树或者链表，
    并插入到哈希桶的对应位置。
    5.2.3、第三种情况，当前位置的 bucket是一个链表，则会进行 链表优化重 hash。
</code></pre><p> <strong>注意：</strong><br> HashMap 每一次的扩容都是在之前的基础上翻倍，那么在容量扩大之后，移动数据的情况就会有一些特别的地方，<br> 不在像JDK1.7 那样重新 hash 找位置。JDK1.8 的做法是把元素的hash值与哈希桶数据的长度-1 作‘与’运算，<br> 判断计算结果为0或者1，为0的情况下，就表示该元素不需要移动位置，反之需。<br> 就是这一行代码  if ((e.hash &amp; oldCap) == 0)  判断是否需要移动位置。</p>
<p> 示例图：<br> 图1：<img src="http://tech.meituan.com/img/java-hashmap/hashMap%201.8%20%E5%93%88%E5%B8%8C%E7%AE%97%E6%B3%95%E4%BE%8B%E5%9B%BE1.png" alt="image"><br>    元素在重新计算 Hash 后，因为哈希桶的长度n变为2倍，那个n-1的mask范围在高位多 1bit，因此新的 index 就会发生这样的变化：<br>    <img src="http://tech.meituan.com/img/java-hashmap/hashMap%201.8%20%E5%93%88%E5%B8%8C%E7%AE%97%E6%B3%95%E4%BE%8B%E5%9B%BE2.png" alt="image"><br> 图2：<img src="http://tech.meituan.com/img/java-hashmap/jdk1.8%20hashMap%E6%89%A9%E5%AE%B9%E4%BE%8B%E5%9B%BE.png" alt="image"></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">final</span> Node&lt;K,V&gt;[] resize() &#123;</span><br><span class="line">        Node&lt;K,V&gt;[] oldTab = table; <span class="comment">// 1</span></span><br><span class="line">        <span class="keyword">int</span> oldCap = (oldTab == <span class="keyword">null</span>) ? <span class="number">0</span> : oldTab.length;</span><br><span class="line">        <span class="keyword">int</span> oldThr = threshold;</span><br><span class="line">        <span class="keyword">int</span> newCap, newThr = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">if</span> (oldCap &gt; <span class="number">0</span>) &#123;  <span class="comment">// 2.1</span></span><br><span class="line">            <span class="keyword">if</span> (oldCap &gt;= MAXIMUM_CAPACITY) &#123;  <span class="comment">// 2.1.1</span></span><br><span class="line">                threshold = Integer.MAX_VALUE;</span><br><span class="line">                <span class="keyword">return</span> oldTab;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span> ((newCap = oldCap &lt;&lt; <span class="number">1</span>) &lt; MAXIMUM_CAPACITY &amp;&amp;</span><br><span class="line">                     oldCap &gt;= DEFAULT_INITIAL_CAPACITY) <span class="comment">// 2.1.2</span></span><br><span class="line">                newThr = oldThr &lt;&lt; <span class="number">1</span>; <span class="comment">// 阈值*2</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (oldThr &gt; <span class="number">0</span>) <span class="comment">// 2.2  容量被阈值设置过</span></span><br><span class="line">            newCap = oldThr;</span><br><span class="line">        <span class="keyword">else</span> &#123;   <span class="comment">// 2.3            // 初始化</span></span><br><span class="line">            newCap = DEFAULT_INITIAL_CAPACITY;</span><br><span class="line">            newThr = (<span class="keyword">int</span>)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (newThr == <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">float</span> ft = (<span class="keyword">float</span>)newCap * loadFactor;</span><br><span class="line">            newThr = (newCap &lt; MAXIMUM_CAPACITY &amp;&amp; ft &lt; (<span class="keyword">float</span>)MAXIMUM_CAPACITY ?</span><br><span class="line">                      (<span class="keyword">int</span>)ft : Integer.MAX_VALUE);</span><br><span class="line">        &#125;</span><br><span class="line">        threshold = newThr;</span><br><span class="line">        <span class="comment">// 5 以下是复制移动元素的过程</span></span><br><span class="line">        <span class="meta">@SuppressWarnings</span>(&#123;<span class="string">"rawtypes"</span>,<span class="string">"unchecked"</span>&#125;)</span><br><span class="line">            Node&lt;K,V&gt;[] newTab = (Node&lt;K,V&gt;[])<span class="keyword">new</span> Node[newCap];</span><br><span class="line">        table = newTab;   <span class="comment">// 5.1</span></span><br><span class="line">        <span class="keyword">if</span> (oldTab != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; oldCap; ++j) &#123;   <span class="comment">// 5.2</span></span><br><span class="line">                Node&lt;K,V&gt; e;</span><br><span class="line">                <span class="keyword">if</span> ((e = oldTab[j]) != <span class="keyword">null</span>) &#123; <span class="comment">//5.2.1</span></span><br><span class="line">                    oldTab[j] = <span class="keyword">null</span>;</span><br><span class="line">                    <span class="keyword">if</span> (e.next == <span class="keyword">null</span>)  <span class="comment">// 5.2.1.1</span></span><br><span class="line">                        newTab[e.hash &amp; (newCap - <span class="number">1</span>)] = e;</span><br><span class="line">                    <span class="keyword">else</span> <span class="keyword">if</span> (e <span class="keyword">instanceof</span> TreeNode) <span class="comment">// 5.2.1.2</span></span><br><span class="line">                        ((TreeNode&lt;K,V&gt;)e).split(<span class="keyword">this</span>, newTab, j, oldCap);</span><br><span class="line">                    <span class="keyword">else</span> &#123; <span class="comment">// preserve order  // 5.2.1.3</span></span><br><span class="line">                        Node&lt;K,V&gt; loHead = <span class="keyword">null</span>, loTail = <span class="keyword">null</span>;</span><br><span class="line">                        Node&lt;K,V&gt; hiHead = <span class="keyword">null</span>, hiTail = <span class="keyword">null</span>;</span><br><span class="line">                        Node&lt;K,V&gt; next;</span><br><span class="line">                        <span class="keyword">do</span> &#123;</span><br><span class="line">                            next = e.next;</span><br><span class="line">                            <span class="keyword">if</span> ((e.hash &amp; oldCap) == <span class="number">0</span>) &#123;</span><br><span class="line">                                <span class="keyword">if</span> (loTail == <span class="keyword">null</span>)</span><br><span class="line">                                    loHead = e;</span><br><span class="line">                                <span class="keyword">else</span></span><br><span class="line">                                    loTail.next = e;</span><br><span class="line">                                loTail = e;</span><br><span class="line">                            &#125;</span><br><span class="line">                            <span class="keyword">else</span> &#123;</span><br><span class="line">                                <span class="keyword">if</span> (hiTail == <span class="keyword">null</span>)</span><br><span class="line">                                    hiHead = e;</span><br><span class="line">                                <span class="keyword">else</span></span><br><span class="line">                                    hiTail.next = e;</span><br><span class="line">                                hiTail = e;</span><br><span class="line">                            &#125;</span><br><span class="line">                        &#125; <span class="keyword">while</span> ((e = next) != <span class="keyword">null</span>);</span><br><span class="line">                        <span class="keyword">if</span> (loTail != <span class="keyword">null</span>) &#123;</span><br><span class="line">                            loTail.next = <span class="keyword">null</span>;</span><br><span class="line">                            newTab[j] = loHead;</span><br><span class="line">                        &#125;</span><br><span class="line">                        <span class="keyword">if</span> (hiTail != <span class="keyword">null</span>) &#123;</span><br><span class="line">                            hiTail.next = <span class="keyword">null</span>;</span><br><span class="line">                            newTab[j + oldCap] = hiHead;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> newTab;</span><br></pre></td></tr></table></figure>
<h4 id="四、HashMap-的线程安全性"><a href="#四、HashMap-的线程安全性" class="headerlink" title="四、HashMap 的线程安全性"></a>四、HashMap 的线程安全性</h4><pre><code>HashMap 是线程不安全的。在多线程的环境下，应尽力避免使用线程不安全的HashMap,
而去使用线程安全的 ConcurrentHashMap。
那么 HashMap 为什么不是线程安全的呢？
HashMap 线程不安全主要还是因为 hash碰撞和扩容导致的。
1：hash 碰撞
eg:有两个线程往 HashMap 中添加元素(putVal)时，正好两个线程添加的元素的key的hash值是一样的。
此时可能就会发生如下情况：
    当线程A执行到 if ((p = tab[i = (n - 1) &amp; hash]) == null) 这行代码并且判断结果为true
    （没有 hash 碰撞），但是还没有执行插入操作；此时CPU把执行资源让给了线程B，正好线程B也执行到该
     if 语句，判断结果也是true(线程A还没有插入)，但是线程B执行插入语句。之后CPU又把资源让给了线程A，
    这时候线程A执行插入就会覆盖线程B插入的数据。
发生在链表插入数据的情况也是如此。
2：扩容
扩容造成线程不安全主要体现在以下两个方面：
2.1、扩容时添加数据
    添加数据时，正好 HashMap 需要扩容，在扩容的过程中会先把创建一个新的空哈希桶数组。
    如果在把旧数据复制到新的哈希桶数组内之前添加数据，那么就不会检查哈希碰撞的问题，
    新加的数据就直接加入了，但是在之后把旧数据复制新的哈希桶数组时，可能就会覆盖新加的数据。
2.2、删除数据
    删除数据的时候正好 HashMap 在执行扩容，但是还没有复制数据。
    此时执行删除，会在新的哈希桶数组中删除数据，但是新的哈希桶数组并没有数据，所有删除操作并没有删除
2.2、扩容时可能会造成死锁
</code></pre>
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/Map/" rel="tag"># Map</a>
          
            <a href="/tags/HashMap/" rel="tag"># HashMap</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2018/11/16/2018-11-16-hashset/" rel="next" title="HashSet">
                <i class="fa fa-chevron-left"></i> HashSet
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2018/11/17/2018-11-17-jvm-class-load-mechanism/" rel="prev" title="JVM类加载机制">
                JVM类加载机制 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope="" itemtype="http://schema.org/Person">
            
              <p class="site-author-name" itemprop="name">sangaizhi</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">18</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">4</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">17</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          

          
          

          
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            
            
              <div class="post-toc-content">  <ol class="nav"><li class="nav-item nav-level-4"><a class="nav-link" href="#一、HashMap-的存储结构"><span class="nav-number">1.</span> <span class="nav-text">一、HashMap 的存储结构</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#二、HashMap-中-put-方法的介绍"><span class="nav-number">2.</span> <span class="nav-text">二、HashMap 中 put() 方法的介绍</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#三、HashMap-的-扩容机制（resize）"><span class="nav-number">3.</span> <span class="nav-text">三、HashMap 的 扩容机制（resize）</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#四、HashMap-的线程安全性"><span class="nav-number">4.</span> <span class="nav-text">四、HashMap 的线程安全性</span></a></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2018</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">sangaizhi</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Muse</a> v5.1.4</div>




        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  

  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  

  

  
  

  

  

  

</body>
</html>
